package de.fuberlin.inf.alp2;

public class CDLList {
	CDLNode sentinel;
	
	/**
	 *  Constructor creates an empty list
	 */
	public CDLList(){
		this.sentinel = new CDLNode(null,null);
		this.sentinel.setNext(this.sentinel);
		this.sentinel.setPrevious(this.sentinel);
	}
	
	/**
	 * The only choice to add items to the list should be this method -
	 * otherwise the correct order can not be ensured.
	 * @param value
	 */
	@SuppressWarnings("unchecked")
    public void insertSorted(Comparable value){
		CDLNode current = this.sentinel.getNext();
		while (current != this.sentinel){
			if (current.getValue().compareTo(value) > -1)
				break;
			current = current.getNext();
		}
		new CDLNode(value, current.getPrevious());
	}
	
	/**
	 * Appends the specified element to the end of this list (correct order not
	 * ensured anymore)
	 * @param value - the element to append to this list
	 */
	@SuppressWarnings("unchecked")
    public void add (Comparable value){
		new CDLNode(value, this.sentinel.getPrevious());
	}
	
	/**
	 * Restore correct order.
	 */
	public void sort(){
		CDLList unsorted = this.clone();
		this.clear();
		CDLNode current = unsorted.sentinel.getNext();
		while (current != unsorted.sentinel){
			this.insertSorted(current.getValue());
			current = current.getNext();
		}
	}
	
	/**
	 * Returns the element at the specified position in this list.
	 * @param index - index of element to return.
	 * @return the element at the specified position in this list. 
	 */
	@SuppressWarnings("unchecked")
    public Comparable get(int index){
		CDLNode current = this.sentinel.getNext();
		for (int i = 0; i < index; i++)
			current = current.getNext();
		return current.getValue();
	}
	
	/**
	 * Returns a shallow copy of this LinkedList. (The values themselves are
	 * not cloned.) 
	 */
	public CDLList clone(){
		CDLList copy = new CDLList();
		CDLNode current = this.sentinel.getNext();
		while (current != this.sentinel)
		{
			copy.add(current.getValue());
			current = current.getNext();
		}
		return copy;
	}
	
	/**
	 * Removes all of the elements from this list. 
	 */
	public void clear(){
		this.sentinel.setNext(this.sentinel);
		this.sentinel.setPrevious(this.sentinel);
	}
	
	@Override
	public String toString(){
		StringBuffer sb = new StringBuffer();
		sb.append("{");
		CDLNode current = this.sentinel.getNext();
		while (current != sentinel){
			sb.append(current.getValue() + ",");
			current = current.getNext();
		}
		if (sb.length() > 1)
			sb.deleteCharAt(sb.length()-1); // (delete last ',')
		sb.append("}");
		return sb.toString();
	}
}
